1、反转链表

class Solution {
  public:
    ListNode* ReverseList(ListNode* pHead) {
        //处理空节点
        if (pHead == NULL) {
            return NULL;
        }
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while (cur != NULL) {
            //断开当前链表
            ListNode* temp = cur->next;
            //当前节点的next改为pre
            cur->next = pre;
            //前置节点改为cur
            pre = cur;
            //当前节点改为保存的temp
            cur = temp;
        }
        return pre;
    }
};


2、二分查找
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here
        int l = 0;
        int r = nums.size() - 1;
        //从数组的首位开始 直到二者相遇
        while(l <= r){
            //每次去检查中间的值
            int m = (l + r)/2;
            if(nums[m] == target)
                return m;
            //进入右区间
            if(nums[m] < target)
                l = m +1;
            //进入左区间
            else
                r = m - 1;
        }
        //未找到
        return -1;
    }
};

3、两个栈实现一个队列
class Solution {
  public:
    //入队列就正常入栈
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        //将第一个栈里边的元素全部放到第二个栈里边
        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }
        //第二个栈的栈顶就是最先进来的元素，即队首
        int res = stack2.top();
        stack2.pop();
        //再将第二个栈中的元素放回第一个栈
        while (!stack2.empty()) {
            stack1.push(stack2.top());
            stack2.pop();
        }
        return res;
    }

  private:
    stack<int> stack1;
    stack<int> stack2;
};

4、两数之和（哈希表）(不熟练)

class Solution {
public:
    /**
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        // write code here
        vector<int> res;
        //创建哈希表，两元组分别表示值、下标
        unordered_map<int, int> hash;
        //在哈希表中寻找target - numbers[i]
        for(int i = 0; i < numbers.size(); i++){
            int temp = target - numbers[i];
            //若是没找到，将此信息计入哈希表中
            if(hash.find(temp) == hash.end()){
                hash[numbers[i]] = i;
            }else{
                //哈希表中记录的是之前的数字，所以都要+1
                res.push_back(hash[temp] + 1);
                res.push_back(i + 1);
            }
        }
        return res;
    }
};


5、双指针（接雨水）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        //排除不能形成容器的情况
        if(height.size() < 2){
            return 0;
        }
        int res = 0;
        //双指针左右值
        int left = 0;
        int right = height.size() - 1;
        //共同遍历完所有的数组
        while(left < right){
            //计算区域水容量
            int capacity = min(height[right], height[left])* (right - left);
            //维护最大值
            res = max(capacity, res);
            //优先舍弃较短的一边
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
};


6、排序
6.1 选择排序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int n = arr.size();
        for(int i = 0; i < n; i++){
            int minn = arr[i];
            int mini = i;
            for(int j = i + 1; j < n; j++){
                if(arr[j] < minn){
                    minn = arr[j];
                    mini = j;
                }
            }
            swap(arr[i], arr[mini]);
        }
        return arr;
    }
};


6.2 快速排序


class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    //快速排序
    int partition(vector<int>& arr, int l, int r){
        int x = arr[l];
        while(l < r){
            while(l < r && arr[r] >= x){
                r--;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] < x) {
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = x;
        return l;
    }
    void quicksort(vector<int>& arr, int l, int r){
        if(l < r){
            int mid = partition(arr, l, r);
            quicksort(arr, l, mid - 1);
            quicksort(arr, mid + 1, r);
        }
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int n = arr.size() - 1;
        quicksort(arr, 0, n);
        return arr;
    }
};

6.3 冒泡排序

//冒泡排序(升序)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size() - 1;
        for (int i = 0 ; i < n; i++ ) {
            bool flag = false;
            for (int j = 0 ; j < n - i ; j++) { 
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    swap(arr[j], arr[j + 1]);
                }
            }
            if (!flag) {
                break;
            }
        }
        return arr;
    }
};


7、递归（括号生成）


class Solution {
public:
    /**
     * @param n int整型 
     * @return string字符串vector
     */
    void recursion(int left, int right, string temp, vector<string>& res, int n){
        //左右括号都用完了，就加入结果
        if(left == n && right == n){
            res.push_back(temp);
            return;
        }
        //使用一次左括号
        if(left < n)
            recursion(left + 1, right, temp + "(", res, n);       
        if(right < n && left > right)
            recursion(left, right + 1, temp + ")", res, n);
    }

    vector<string> generateParenthesis(int n) {
        // 记录结果
        vector<string> res;
        //记录每次组装的字符串
        string temp;
        //递归
        recursion(0, 0, temp, res, n);
        return res;        
    }
};

8、C语言冒泡降序排序

void BubbleSort(double arr[], int n) {
    double temp;
    for(int i = 0; i < n; i++) {
        bool flag = false;
        for(int j = 0; j < n - i; j++) {
            if(arr[j] < arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if(!flag) {
            return;
        }
    }
}

9、二维数组元素互换

//str1[2][3];  str2[3][2];  
for(int i = 0; i < 2; i++) {
    for(int j = 0; j < 3; j++) {
        strw[j][i] = str1[i][j]; 
    }
}

10、给定字符串区域搜索字符

int search(char* cpSource, int n,char ch) {
    for(int i = 0; (i < n) && (*(cpSource + 1) != ch); i++) {}
    return i;
}

11、将字符串逆序

void reverseStr(char* father, char* child) {
    int j = 0;
    char temp[100];
    while(father[j]) {
        temp[j] = father[j];
        j++;
        if(j > 99) {
            return;
        }
    }
    for(int i = 0; i < j; i++) {
        child[i] = temp[j - i - 1];
    }
    child[i] = '\0';
}

12、判断链表是否有环

int testListRing(ListNode* pHead) {
    ListNode* pFast = pHead;
    ListNode* PSlow = pHead;

    while(pFast->next && pSlow->next) {
        pFast = pFast->next->next;
        pSlow = pSlow->next;
        if(pFast == NULL) {
            return 0;
        }
        if(pFast == pSlow) {
            return 1;
        }
    }
    return 0;
}

13、整数转字符串

void IntToCharChange(int num, char* pval) {
    char strval[100];
    int val_0 = 0;
    int val_1 = 0;
    int maxlength = 0;
    for(int i = 0; i < 100; i++) {
        val_0 = num % 10;
        val_1 = num / 10;
        strval[i] = val_0 + 48;
        if(val_1 < 10) {
            i++;
            strval[i] = val_1 + 48;
            maxlength = i;
            break;
        }
    }
    for(int j = 0; j < maxlength; j++) {
        pval[j] = strval[maxlength - j];
    }
    pval[++maxlength] = '\0';
}

14、自己实现strcmp

int mystrcmp(const char* str1, const char* str2) {
    assert((str1 != NULL) && (str2 != NULL));

    int ret = 0;
    while(!(ret = *(unsigned char*)str1 - *(unsigned char*)str2)) {
        str1++;
        str2++;
    }
    if(ret > 0) {
        return 1;
    }else if (ret < 0) {
        return -1;
    }
}

15、字符串转整型

int stringToInt(char* str) {
    int num = 0;
    while(*str = '\0') {
        int temp = *str - 48;
        num = num*10 + temp;
        str++;
    }
    return num;
}

16、链表内指定区间反转

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n){
        //加个表头
        ListNode* res = new ListNode(-1);
        res->next = head;
        //前序节点
        ListNode* pre = res;
        //当前节点
        ListNode* cur = head;
        for(int i = 1; i < m; i++){
            pre = cur;
            cur = cur->next;
        }
        //从m反转到n
        for(int i = m; i < n; i++){
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        //返回去掉表头
        return res->next;
    }
};



17、大小写字母转换

// #include <stdio.h>
// #include <string.h>

void Conversion(char* str) {
    int maxlength = strlen(str);
    char temp;
    for(int i= 0; i < maxlength; i++) {
        temp = str[i];
        if(temp >= 'a' && temp <= 'z') {
            str[i] = temp - 32;
        }
        /*
        if(temp >= 'A' && temp <= 'Z') {
            str[i] = temp + 32;
        }
        */

    }
}

int main(){

    char str[100];
    printf("Please input ->>>> \n");
    scanf("%s", str);

    Conversion(str);

    printf("Print string %s \n", str);

    return 0;
}




